// Package _5_拓扑排序算法 main
// @Title _5_拓扑排序算法
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-01-17 13:43
// @Create  2022-01-17 13:43
package main

/**
	要求有向图，且有入度为0的点，并且没有环
编译顺序，依赖关系
*/
type Edge struct {
	Weight int   // 权重（距离）
	From   *Node // 从哪里来
	To     *Node // 到哪里去
}

type Node struct {
	Val  int     // 实际的数据项
	In   int     // 入度，有多少个点，所发散的边是指向自己的 { 无向图的入度= 出度}
	Out  int     // 出度，自己发散出去多少个边
	Next []*Node // 临接的点集
	Edge []*Edge // 临接的边集
}

type Graph struct {
	Node map[int]*Node   // 点集 编码-> 实际的点
	Edge map[*Edge]*Edge // 边集
}

func sortedTopology(g *Graph) {
	inMap := make(map[*Node]int)
	queue := []*Node{}
	for i := 0; i < len(g.Node); i++ {
		inMap[g.Node[i]] = g.Node[i].Val
		if g.Node[i].In == 0 {
			queue = append(queue, g.Node[i])
		}
	}
	// 拓扑排序后的结果
	result := []*Node{}
	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		result = append(result, cur)
		for i := 0; i < len(cur.Next); i++ {
			inMap[cur.Next[i]] = cur.Next[i].Val - 1
			if inMap[cur.Next[i]] == 0 {
				queue = append(queue, cur.Next[i])
			}
		}
	}
}
